import com.sun.org.apache.xpath.internal.axes.SelfIteratorNoPredicate;

import javax.jnlp.SingleInstanceListener;
import java.util.*;

public class Test {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList();  //注意单向队列不可以当作栈来使用
        //Stack<Integer> stack = new LinkedList<>();  //有问题 后面尖括号报错了

        //双端队列可以当作栈来使用
        Deque<Integer> stack2 = new LinkedList<>();
        stack2.push(1);
        Deque<Integer> stack3 = new ArrayDeque<>();  //底层是个数组

        stack3.push(1);  //Deque接口中是有push方法的，以及栈的一些方法，所以双端队列是可以当作栈来使用的

        /**   注意这种写法是很少的，一般不用具体的类去实现具体的对象
         *    都是拿接口去实现对象，这样的话对象的引用就只能调用接口里的方法，就可以知道这个对象是当作什么来使用的
         *
         *    若是下面这种写法，方法有很多，读代码的时候，不知道linkedList是当作 双向链表 ， 栈 来使用 还是队列 或者 双端队列 来使用的
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();
         */
    }

    //力扣150.逆波兰表达式求值 (中等题目)
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x : tokens) {
            if (!(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/"))) {
                stack.push(Integer.parseInt(x));    //放入的时候转变为数字
                //注意转化为整型的方法
            } else {
                int num2 = stack.pop();   //要转换成数字  num2在运算符右边
                int num1 = stack.pop();   //要转换成数字  num1在运算符左边
                switch (x) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    //力扣20.括号匹配问题 (简单题目)
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (s.charAt(i) == ('(') || s.charAt(i) == ('{') || s.charAt(i) == ('[')) {
                stack.push(s.charAt(i));
            } else {
                //遇到了右括号
                if (stack.empty()) {
                    return false;
                }
                char ch2 = stack.peek();//左括号
                if (ch == ')' && ch2 == '(' || ch == '}' && ch2 == '{' || ch == ']' && ch2 == '[') {
                    stack.pop();
                } else {
                    return false;//不匹配
                }
            }
        }
        //注意还要检查是不是多左括号
        if(!stack.empty()) {
            return false;
        }
        return true;
    }


    //牛客JZ31 栈的压入，弹出序列（中等题目）
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            //先放进去，然后看一下是不是和popA中的第一个相等
            //若相等出栈，继续比较后面的，若不相等，继续放入元素
            stack.push(pushA[i]);
            while(j < popA.length && !stack.empty() && stack.peek().equals(popA[j])) {
                stack.pop();
                j++;
            }
        }
        //最后判断栈中是不是空的，若是空的，则返回true，若不空，则返回false
        return stack.empty();
    }


    //力扣155.最小栈(中等题目)
    class MinStack {
        private Stack<Integer> stack;
        private Stack<Integer> minStack;

        public MinStack() {
            stack = new Stack<>();
            minStack = new Stack<>();
        }

        //压栈
        public void push(int val) {
            stack.push(val);
            if(minStack.empty()) {
                minStack.push(val);
            }else {
                if(val <= minStack.peek()) {
                    minStack.push(val);
                }
            }
        }
        //出栈
        public void pop() {
            int val = stack.pop();
            if(val == minStack.peek()) {
                minStack.pop();
            }
        }
        //peek 获取栈顶元素
        public int top() {
            return stack.peek();
        }
        //得到最小值
        public int getMin() {
            return minStack.peek();
        }
    }


    //力扣622.设计循环队列(中等)  (自己写的)
    static class MyCircularQueue2 {

        public int[] elem;
        public int front;
        public int rear;
        public MyCircularQueue2(int k) {
            //注意我们此处是浪费一个空间来表示数组满和不满的，所以要加1
            //注意我们这个浪费的空间是变化的，一直都是front前面的那个空间是浪费的
            elem = new int[k + 1];
        }
        //入队列
        public boolean enQueue(int value) {
            if(isFull()) {
                return false;
            }
            int val = rear  % elem.length;
            /**
             *          //注意这种写法，没有真正让rear = (rear + 1) % elem.length
             *          elem[rear  % elem.length] = value;
             *          rear++;
             */
            elem[val] = value;
            rear = ++val;
            return true;     //注意经过调试后知道，应该是先让rear++，在除以数组的长度，这样才不大于等于数组长度
                             //若是先除以数组长度，再加1，
        }

        //删除，即出队列
        public boolean deQueue() {
            if(isEmpty()) {
                return false;
            }
            front = (front + 1) % elem.length;
            return true;
        }

        //获取队头元素
        public int Front() {
            if(isEmpty()) {
                return -1;
            }
            return elem[front];
        }

        //获取队尾元素
        public int Rear() {
            if(isEmpty()) {
                return -1;
            }
            return elem[(rear - 1 )% elem.length];
        }

        public boolean isEmpty() {
            return rear == front;
        }

        public boolean isFull() {
            return (rear + 1) % elem.length ==  front;
        }
    }


    //博哥写的
    static  class MyCircularQueue {

        private int[] elem;
        private int front;//表示队列的头
        private int rear;//表示队列的尾

        public MyCircularQueue(int k) {
            //如果是浪费空间 这里必须处理多加一个1
            this.elem = new int[k+1];
        }

        /**
         * 入队列
         * @param value
         * @return
         */
        public boolean enQueue(int value) {
            //1、检查是否队列是满的
            if(isFull()){
                return false;
            }
            //2、
            elem[rear] = value;
            //rear++;
            rear = (rear+1) % elem.length;
            return true;
        }

        /**
         * 出队列
         * @return
         */
        public boolean deQueue() {
            if(isEmpty()) {
                return false;
            }
            //front++;
            front = (front+1) % elem.length;
            return true;
        }

        /**
         * 得到队头元素
         * @return
         */
        public int Front() {
            if(isEmpty()) {
                return -1;
            }
            return elem[front];
        }

        /**
         * 得到队尾元素
         * @return
         */
        public int Rear() {
            if(isEmpty()) {
                return -1;
            }
            int index = (rear == 0) ? elem.length-1 : rear-1;
            return elem[index];
        }

        public boolean isEmpty() {
            return front == rear;
        }

        /**
         * 队列是否为满
         * @return
         */
        public boolean isFull() {
       /* if( (rear+1) % elem.length == front) {
            return true;
        }
        return false;*/
            return (rear+1) % elem.length == front;
        }
    }
    public static void main1(String[] args) {

        Test.MyCircularQueue myCircularQueue= new MyCircularQueue(3);
        myCircularQueue.enQueue(1);
        myCircularQueue.enQueue(2);
        myCircularQueue.enQueue(3);
        myCircularQueue.enQueue(4);

        int ret = myCircularQueue.Rear();
        System.out.println(ret);
        myCircularQueue.deQueue();
        myCircularQueue.deQueue();
        myCircularQueue.enQueue(5);
        //myCircularQueue.enQueue(6);
        //myCircularQueue.enQueue(7);
         ret = myCircularQueue.Rear();
        System.out.println(ret);
    }

    //力扣225.用队列实现栈 (简单题目)  要用到两个队列
    class MyStack {

        private Queue<Integer> queue1;
        private Queue<Integer> queue2;
        public MyStack() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        //放入操作，谁不为空，放入到哪个
        public void push(int x) {
            if(!queue1.isEmpty()) {
                queue1.offer(x);
            } else if(!queue2.isEmpty()) {
                queue2.offer(x);
            }else {
                queue1.offer(x);
            }
        }

        //出栈  :  思路就是  哪个不为空，把他里面的前n - 1个元素倒到另一个队列中去，最后一个元素就是要pop出去的
        public int pop() {
            if(empty()) {
                return -1;   //两个队列都为空，意味着栈为空
            }
            if(!queue1.isEmpty()) {
                int size = queue1.size();
                int val = -1;
                while(size != 1) {
                    val = queue1.poll();
                    queue2.offer(val);
                    size--;
                }
                return queue1.poll();
            }else {
                int size = queue2.size();
                int val = -1;
                while(size != 1) {
                    val = queue2.poll();
                    queue1.offer(val);
                    size--;
                }
                return queue2.poll();
            }
        }

        //相当于peek
        public int top() {
            if(empty()) {
                return -1;   //两个队列都为空，意味着栈为空
            }
            if(!queue1.isEmpty()) {
                int size = queue1.size();
                int val = -1;
                while(size != 0) {
                    val = queue1.poll();
                    queue2.offer(val);
                    size--;
                }
                return val;
            }else {
                int size = queue2.size();
                int val = -1;
                while(size != 0) {
                    val = queue2.poll();
                    queue1.offer(val);
                    size--;
                }
                return val;
            }
        }

        public boolean empty() {
            return queue1.isEmpty() && queue2.isEmpty();
        }
    }


    //力扣232.用栈实现队列
    class MyQueue {
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;
        public MyQueue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

        //入栈  思路都入到s1中去，pop的时候全部挪s2中去，在弹出栈顶元素即可，相当于掉个顺序
        public void push(int x) {
            stack1.push(x);
        }

        public int pop() {
            if(!stack2.empty()) {
                return stack2.pop();
            }
            //上面有return，说明走到这s2空了，那么s1中的全部挪到s2中
            int size = stack1.size();
            while (size != 0) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

        public int peek() {
            if(!stack2.empty()) {
                return stack2.peek();
            }
            //上面有return，说明走到这s2空了，那么s1中的全部挪到s2中
            int size = stack1.size();
            while (size != 0) {
                stack2.push(stack1.pop());
                size--;
            }
            return stack2.peek();
        }

        public boolean empty() {
            return stack1.empty() && stack2.empty();
        }
    }
}
